//#include "StdAfx.h"
#include "UPO_solver.h"

using namespace std;


UPO_solver::UPO_solver(InputData* _inputMatrix)
	: inputMatrix(NULL),
	CurrentNodesMask(NULL)
{
	inputMatrix = _inputMatrix;

	// Init current best solution to contain all nodes, because that is primitive solution
	currentBestSolution.activeNodes = inputMatrix->getMatrixDimension();
	currentBestSolution.solutionMask = new bool[inputMatrix->getMatrixDimension()];
	for (int i = 0; i < inputMatrix->getMatrixDimension(); i++)
	{
		currentBestSolution.solutionMask[i] = true;
	}

	
	// Set current solution mask to all zeros
	CurrentNodesMask = new bool[inputMatrix->getMatrixDimension()];
	for (int i = 0; i < inputMatrix->getMatrixDimension(); i++)
	{
		CurrentNodesMask[i] = false;
	}
}

UPO_solver::~UPO_solver()
{
	SystemState state;
	
	if (currentBestSolution.solutionMask != NULL)
		delete [] currentBestSolution.solutionMask;

	// Tohle by melo smazat globalni masku reseni ale program mi tady crashne, nechapu proc, a kdyz je to 
	// takhle zakomentovany tak to ani nenahlasi zadne leaky, takze nevim kdo to maze driv
	//if (CurrentNodesMask != NULL)
	//	delete [] CurrentNodesMask;
		
	for (unsigned int i = 0; i < MainStack.size(); i++)
	{
		state = MainStack.top();
		//delete [] state; //state aren't made dynamically!!
		MainStack.pop();
	}
}

void UPO_solver::WriteSolutionMask()
{
	for(int i = 0; i < inputMatrix->getMatrixDimension(); i++)
	{
		cout << currentBestSolution.solutionMask[i] << " ";
	}
	
	cout << endl;
}

void UPO_solver::Solve()
{
	bool bPushState;
	int totalNodes;
	int iRow;
	int a, i;
	// Empty MainStack if there is something left
	for (unsigned int i = 0; i < MainStack.size(); i++)
	{
		MainStack.pop();
	}

	// Get total number of nodes
	totalNodes = inputMatrix->getMatrixDimension();

	// Create first root state to start DFS
	SystemState state;
	state.totalNodes = totalNodes;
	state.coveredLines = 0;
	state.indexToNodes = 0;
	state.targetNode = -1;

	// Add root to stack
	MainStack.push(state);

	while(!MainStack.empty()) // While we have something on stack
	{
		// Get top of the stack
		SystemState actualState = MainStack.top();
		// Remove top from stack
		MainStack.pop();

		// Get index to array of nodes
		iRow = actualState.indexToNodes;
		actualState.indexToNodes++;

		//  If index is out of bounds or number of active nodes is bigger or same as current best solution => break this branch
		if (actualState.indexToNodes > totalNodes || GetActiveNodesNumber(CurrentNodesMask,totalNodes) >= currentBestSolution.activeNodes-1)
		{
			CurrentNodesMask[actualState.targetNode] = false; // Set flag of this node to true in nodes mask (=we added this node)
			continue;
		}
		MainStack.push(actualState);

		// Generate a new node by expanding the current one
		bool bPushState = true;
		SystemState newState;
		newState.CopyState(actualState); // Make a copy of current one
		newState.targetNode = iRow;

		CurrentNodesMask[iRow] = true; // Set flag of this node to true in nodes mask (=we added this node)
		
		// Get all new edges from the new created node
		for (int i = 0; i < totalNodes; i++ )
		{				
			if (inputMatrix->matrix[iRow][i] == 1
				&& CurrentNodesMask[i] == false)
			{
				newState.coveredLines++;
				// If covered edges == total number of edges, we found current best solution
				if (newState.coveredLines == inputMatrix->getEdgesNumber())
				{
					currentBestSolution.CopyMask(CurrentNodesMask,totalNodes);
					currentBestSolution.activeNodes = GetActiveNodesNumber(CurrentNodesMask,totalNodes); 
					bPushState = false;
				}
			}
		}

		// If new state is still on our promising way, put it on the stack
		if (bPushState == true && GetActiveNodesNumber(CurrentNodesMask,totalNodes) < currentBestSolution.activeNodes - 1)
		{
			MainStack.push(newState);
		}
		else
		{	
			// if this branch is not promising or it was solution backtrack and set its position in mask to 0
			CurrentNodesMask[iRow] = false;
		}
	}
}


int UPO_solver::GetActiveNodesNumber(bool* mask, int iNodes)
{
	int activeNodes = 0;
	for(int i = 0; i < iNodes; i++)
	{
		if (mask[i] == true)
			activeNodes++;
	}
	return activeNodes;
}